package com.lihepeng.leecode.leetcodeDataStruct.easy;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 *
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 *
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution88 {
    //逆向双指针
    public void merge01(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }

    // 双指针 算法
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 双指针  方法
        int p1=0,p2=0;
        int[] sortNums = new int[m+n];
        int cur ;
        while (p1<m || p2<n){
            if (p1 ==m){
                // 结束
                cur = nums2[p2++];
            }else if (p2 == n){
                cur = nums1[p1++];
            }else if (nums1[p1]<nums2[p2]){
                cur = nums1[p1++];
            }else {
                cur = nums2[p2++];
            }
            sortNums[p1+p2-1] = cur;
        }
        for (int i=0;i!=m+n;i++){
            nums1[i] = sortNums[i];
        }
    }
    @Test
    public void runTest(){
        int[]arr1 = {1,3,5,7};
        int size1 = 2;
        int []arr2 = {2,4,6,8};
        int size2 = 2;
        this.merge(arr1,size1,arr2,size2);
        System.out.println(Arrays.toString(arr1));
    }

}
